home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1998 November / Freeware November 1998.img / dist / fw_emacs.idb / usr / freeware / info / cl-4.z / cl-4 (.txt)
GNU Info File  |  1998-10-27  |  45KB  |  772 lines

  1. This is Info file ../info/cl, produced by Makeinfo-1.64 from the input
  2. file cl.texi.
  3.    This file documents the GNU Emacs Common Lisp emulation package.
  4.    Copyright (C) 1993 Free Software Foundation, Inc.
  5.    Permission is granted to make and distribute verbatim copies of this
  6. manual provided the copyright notice and this permission notice are
  7. preserved on all copies.
  8.    Permission is granted to copy and distribute modified versions of
  9. this manual under the conditions for verbatim copying, provided also
  10. that the section entitled "GNU General Public License" is included
  11. exactly as in the original, and provided that the entire resulting
  12. derived work is distributed under the terms of a permission notice
  13. identical to this one.
  14.    Permission is granted to copy and distribute translations of this
  15. manual into another language, under the above conditions for modified
  16. versions, except that the section entitled "GNU General Public License"
  17. may be included in a translation approved by the author instead of in
  18. the original English.
  19. File: cl,  Node: Implementation Parameters,  Prev: Random Numbers,  Up: Numbers
  20. Implementation Parameters
  21. =========================
  22. This package defines several useful constants having to with numbers.
  23.  - Variable: most-positive-fixnum
  24.      This constant equals the largest value a Lisp integer can hold.
  25.      It is typically `2^23-1' or `2^25-1'.
  26.  - Variable: most-negative-fixnum
  27.      This constant equals the smallest (most negative) value a Lisp
  28.      integer can hold.
  29.    The following parameters have to do with floating-point numbers.
  30. This package determines their values by exercising the computer's
  31. floating-point arithmetic in various ways.  Because this operation
  32. might be slow, the code for initializing them is kept in a separate
  33. function that must be called before the parameters can be used.
  34.  - Function: cl-float-limits
  35.      This function makes sure that the Common Lisp floating-point
  36.      parameters like `most-positive-float' have been initialized.
  37.      Until it is called, these parameters will be `nil'.  If this
  38.      version of Emacs does not support floats (e.g., most versions of
  39.      Emacs 18), the parameters will remain `nil'.  If the parameters
  40.      have already been initialized, the function returns immediately.
  41.      The algorithm makes assumptions that will be valid for most modern
  42.      machines, but will fail if the machine's arithmetic is extremely
  43.      unusual, e.g., decimal.
  44.    Since true Common Lisp supports up to four different floating-point
  45. precisions, it has families of constants like
  46. `most-positive-single-float', `most-positive-double-float',
  47. `most-positive-long-float', and so on.  Emacs has only one
  48. floating-point precision, so this package omits the precision word from
  49. the constants' names.
  50.  - Variable: most-positive-float
  51.      This constant equals the largest value a Lisp float can hold.  For
  52.      those systems whose arithmetic supports infinities, this is the
  53.      largest *finite* value.  For IEEE machines, the value is
  54.      approximately `1.79e+308'.
  55.  - Variable: most-negative-float
  56.      This constant equals the most-negative value a Lisp float can hold.
  57.      (It is assumed to be equal to `(- most-positive-float)'.)
  58.  - Variable: least-positive-float
  59.      This constant equals the smallest Lisp float value greater than
  60.      zero.  For IEEE machines, it is about `4.94e-324' if denormals are
  61.      supported or `2.22e-308' if not.
  62.  - Variable: least-positive-normalized-float
  63.      This constant equals the smallest *normalized* Lisp float greater
  64.      than zero, i.e., the smallest value for which IEEE denormalization
  65.      will not result in a loss of precision.  For IEEE machines, this
  66.      value is about `2.22e-308'.  For machines that do not support the
  67.      concept of denormalization and gradual underflow, this constant
  68.      will always equal `least-positive-float'.
  69.  - Variable: least-negative-float
  70.      This constant is the negative counterpart of
  71.      `least-positive-float'.
  72.  - Variable: least-negative-normalized-float
  73.      This constant is the negative counterpart of
  74.      `least-positive-normalized-float'.
  75.  - Variable: float-epsilon
  76.      This constant is the smallest positive Lisp float that can be added
  77.      to 1.0 to produce a distinct value.  Adding a smaller number to 1.0
  78.      will yield 1.0 again due to roundoff.  For IEEE machines, epsilon
  79.      is about `2.22e-16'.
  80.  - Variable: float-negative-epsilon
  81.      This is the smallest positive value that can be subtracted from
  82.      1.0 to produce a distinct value.  For IEEE machines, it is about
  83.      `1.11e-16'.
  84. File: cl,  Node: Sequences,  Next: Lists,  Prev: Numbers,  Up: Top
  85. Sequences
  86. *********
  87. Common Lisp defines a number of functions that operate on "sequences",
  88. which are either lists, strings, or vectors.  Emacs Lisp includes a few
  89. of these, notably `elt' and `length'; this package defines most of the
  90. rest.
  91. * Menu:
  92. * Sequence Basics::          Arguments shared by all sequence functions
  93. * Mapping over Sequences::   `mapcar*', `mapcan', `map', `every', etc.
  94. * Sequence Functions::       `subseq', `remove*', `substitute', etc.
  95. * Searching Sequences::      `find', `position', `count', `search', etc.
  96. * Sorting Sequences::        `sort*', `stable-sort', `merge'
  97. File: cl,  Node: Sequence Basics,  Next: Mapping over Sequences,  Prev: Sequences,  Up: Sequences
  98. Sequence Basics
  99. ===============
  100. Many of the sequence functions take keyword arguments; *note Argument
  101. Lists::..  All keyword arguments are optional and, if specified, may
  102. appear in any order.
  103.    The `:key' argument should be passed either `nil', or a function of
  104. one argument.  This key function is used as a filter through which the
  105. elements of the sequence are seen; for example, `(find x y :key 'car)'
  106. is similar to `(assoc* x y)': It searches for an element of the list
  107. whose `car' equals `x', rather than for an element which equals `x'
  108. itself.  If `:key' is omitted or `nil', the filter is effectively the
  109. identity function.
  110.    The `:test' and `:test-not' arguments should be either `nil', or
  111. functions of two arguments.  The test function is used to compare two
  112. sequence elements, or to compare a search value with sequence elements.
  113. (The two values are passed to the test function in the same order as
  114. the original sequence function arguments from which they are derived,
  115. or, if they both come from the same sequence, in the same order as they
  116. appear in that sequence.) The `:test' argument specifies a function
  117. which must return true (non-`nil') to indicate a match; instead, you
  118. may use `:test-not' to give a function which returns *false* to
  119. indicate a match.  The default test function is `:test 'eql'.
  120.    Many functions which take ITEM and `:test' or `:test-not' arguments
  121. also come in `-if' and `-if-not' varieties, where a PREDICATE function
  122. is passed instead of ITEM, and sequence elements match if the predicate
  123. returns true on them (or false in the case of `-if-not').  For example:
  124.      (remove* 0 seq :test '=)  ==  (remove-if 'zerop seq)
  125. to remove all zeros from sequence `seq'.
  126.    Some operations can work on a subsequence of the argument sequence;
  127. these function take `:start' and `:end' arguments which default to zero
  128. and the length of the sequence, respectively.  Only elements between
  129. START (inclusive) and END (exclusive) are affected by the operation.
  130. The END argument may be passed `nil' to signify the length of the
  131. sequence; otherwise, both START and END must be integers, with `0 <=
  132. START <= END <= (length SEQ)'.  If the function takes two sequence
  133. arguments, the limits are defined by keywords `:start1' and `:end1' for
  134. the first, and `:start2' and `:end2' for the second.
  135.    A few functions accept a `:from-end' argument, which, if non-`nil',
  136. causes the operation to go from right-to-left through the sequence
  137. instead of left-to-right, and a `:count' argument, which specifies an
  138. integer maximum number of elements to be removed or otherwise processed.
  139.    The sequence functions make no guarantees about the order in which
  140. the `:test', `:test-not', and `:key' functions are called on various
  141. elements.  Therefore, it is a bad idea to depend on side effects of
  142. these functions.  For example, `:from-end' may cause the sequence to be
  143. scanned actually in reverse, or it may be scanned forwards but
  144. computing a result "as if" it were scanned backwards.  (Some functions,
  145. like `mapcar*' and `every', *do* specify exactly the order in which the
  146. function is called so side effects are perfectly acceptable in those
  147. cases.)
  148.    Strings in GNU Emacs 19 may contain "text properties" as well as
  149. character data.  Except as noted, it is undefined whether or not text
  150. properties are preserved by sequence functions.  For example, `(remove*
  151. ?A STR)' may or may not preserve the properties of the characters
  152. copied from STR into the result.
  153. File: cl,  Node: Mapping over Sequences,  Next: Sequence Functions,  Prev: Sequence Basics,  Up: Sequences
  154. Mapping over Sequences
  155. ======================
  156. These functions "map" the function you specify over the elements of
  157. lists or arrays.  They are all variations on the theme of the built-in
  158. function `mapcar'.
  159.  - Function: mapcar* FUNCTION SEQ &rest MORE-SEQS
  160.      This function calls FUNCTION on successive parallel sets of
  161.      elements from its argument sequences.  Given a single SEQ argument
  162.      it is equivalent to `mapcar'; given N sequences, it calls the
  163.      function with the first elements of each of the sequences as the N
  164.      arguments to yield the first element of the result list, then with
  165.      the second elements, and so on.  The mapping stops as soon as the
  166.      shortest sequence runs out.  The argument sequences may be any
  167.      mixture of lists, strings, and vectors; the return sequence is
  168.      always a list.
  169.      Common Lisp's `mapcar' accepts multiple arguments but works only
  170.      on lists; Emacs Lisp's `mapcar' accepts a single sequence
  171.      argument.  This package's `mapcar*' works as a compatible superset
  172.      of both.
  173.  - Function: map RESULT-TYPE FUNCTION SEQ &rest MORE-SEQS
  174.      This function maps FUNCTION over the argument sequences, just like
  175.      `mapcar*', but it returns a sequence of type RESULT-TYPE rather
  176.      than a list.  RESULT-TYPE must be one of the following symbols:
  177.      `vector', `string', `list' (in which case the effect is the same
  178.      as for `mapcar*'), or `nil' (in which case the results are thrown
  179.      away and `map' returns `nil').
  180.  - Function: maplist FUNCTION LIST &rest MORE-LISTS
  181.      This function calls FUNCTION on each of its argument lists, then
  182.      on the `cdr's of those lists, and so on, until the shortest list
  183.      runs out.  The results are returned in the form of a list.  Thus,
  184.      `maplist' is like `mapcar*' except that it passes in the list
  185.      pointers themselves rather than the `car's of the advancing
  186.      pointers.
  187.  - Function: mapc FUNCTION SEQ &rest MORE-SEQS
  188.      This function is like `mapcar*', except that the values returned
  189.      by FUNCTION are ignored and thrown away rather than being
  190.      collected into a list.  The return value of `mapc' is SEQ, the
  191.      first sequence.
  192.  - Function: mapl FUNCTION LIST &rest MORE-LISTS
  193.      This function is like `maplist', except that it throws away the
  194.      values returned by FUNCTION.
  195.  - Function: mapcan FUNCTION SEQ &rest MORE-SEQS
  196.      This function is like `mapcar*', except that it concatenates the
  197.      return values (which must be lists) using `nconc', rather than
  198.      simply collecting them into a list.
  199.  - Function: mapcon FUNCTION LIST &rest MORE-LISTS
  200.      This function is like `maplist', except that it concatenates the
  201.      return values using `nconc'.
  202.  - Function: some PREDICATE SEQ &rest MORE-SEQS
  203.      This function calls PREDICATE on each element of SEQ in turn; if
  204.      PREDICATE returns a non-`nil' value, `some' returns that value,
  205.      otherwise it returns `nil'.  Given several sequence arguments, it
  206.      steps through the sequences in parallel until the shortest one
  207.      runs out, just as in `mapcar*'.  You can rely on the left-to-right
  208.      order in which the elements are visited, and on the fact that
  209.      mapping stops immediately as soon as PREDICATE returns non-`nil'.
  210.  - Function: every PREDICATE SEQ &rest MORE-SEQS
  211.      This function calls PREDICATE on each element of the sequence(s)
  212.      in turn; it returns `nil' as soon as PREDICATE returns `nil' for
  213.      any element, or `t' if the predicate was true for all elements.
  214.  - Function: notany PREDICATE SEQ &rest MORE-SEQS
  215.      This function calls PREDICATE on each element of the sequence(s)
  216.      in turn; it returns `nil' as soon as PREDICATE returns a non-`nil'
  217.      value for any element, or `t' if the predicate was `nil' for all
  218.      elements.
  219.  - Function: notevery PREDICATE SEQ &rest MORE-SEQS
  220.      This function calls PREDICATE on each element of the sequence(s)
  221.      in turn; it returns a non-`nil' value as soon as PREDICATE returns
  222.      `nil' for any element, or `t' if the predicate was true for all
  223.      elements.
  224.  - Function: reduce FUNCTION SEQ &key :from-end :start :end
  225.           :initial-value :key
  226.      This function combines the elements of SEQ using an associative
  227.      binary operation.  Suppose FUNCTION is `*' and SEQ is the list `(2
  228.      3 4 5)'.  The first two elements of the list are combined with `(*
  229.      2 3) = 6'; this is combined with the next element, `(* 6 4) = 24',
  230.      and that is combined with the final element: `(* 24 5) = 120'.
  231.      Note that the `*' function happens to be self-reducing, so that
  232.      `(* 2 3 4 5)' has the same effect as an explicit call to `reduce'.
  233.      If `:from-end' is true, the reduction is right-associative instead
  234.      of left-associative:
  235.           (reduce '- '(1 2 3 4))
  236.                == (- (- (- 1 2) 3) 4) => -8
  237.           (reduce '- '(1 2 3 4) :from-end t)
  238.                == (- 1 (- 2 (- 3 4))) => -2
  239.      If `:key' is specified, it is a function of one argument which is
  240.      called on each of the sequence elements in turn.
  241.      If `:initial-value' is specified, it is effectively added to the
  242.      front (or rear in the case of `:from-end') of the sequence.  The
  243.      `:key' function is *not* applied to the initial value.
  244.      If the sequence, including the initial value, has exactly one
  245.      element then that element is returned without ever calling
  246.      FUNCTION.  If the sequence is empty (and there is no initial
  247.      value), then FUNCTION is called with no arguments to obtain the
  248.      return value.
  249.    All of these mapping operations can be expressed conveniently in
  250. terms of the `loop' macro.  In compiled code, `loop' will be faster
  251. since it generates the loop as in-line code with no function calls.
  252. File: cl,  Node: Sequence Functions,  Next: Searching Sequences,  Prev: Mapping over Sequences,  Up: Sequences
  253. Sequence Functions
  254. ==================
  255. This section describes a number of Common Lisp functions for operating
  256. on sequences.
  257.  - Function: subseq SEQUENCE START &optional END
  258.      This function returns a given subsequence of the argument
  259.      SEQUENCE, which may be a list, string, or vector.  The indices
  260.      START and END must be in range, and START must be no greater than
  261.      END.  If END is omitted, it defaults to the length of the
  262.      sequence.  The return value is always a copy; it does not share
  263.      structure with SEQUENCE.
  264.      As an extension to Common Lisp, START and/or END may be negative,
  265.      in which case they represent a distance back from the end of the
  266.      sequence.  This is for compatibility with Emacs' `substring'
  267.      function.  Note that `subseq' is the *only* sequence function that
  268.      allows negative START and END.
  269.      You can use `setf' on a `subseq' form to replace a specified range
  270.      of elements with elements from another sequence.  The replacement
  271.      is done as if by `replace', described below.
  272.  - Function: concatenate RESULT-TYPE &rest SEQS
  273.      This function concatenates the argument sequences together to form
  274.      a result sequence of type RESULT-TYPE, one of the symbols
  275.      `vector', `string', or `list'.  The arguments are always copied,
  276.      even in cases such as `(concatenate 'list '(1 2 3))' where the
  277.      result is identical to an argument.
  278.  - Function: fill SEQ ITEM &key :start :end
  279.      This function fills the elements of the sequence (or the specified
  280.      part of the sequence) with the value ITEM.
  281.  - Function: replace SEQ1 SEQ2 &key :start1 :end1 :start2 :end2
  282.      This function copies part of SEQ2 into part of SEQ1.  The sequence
  283.      SEQ1 is not stretched or resized; the amount of data copied is
  284.      simply the shorter of the source and destination (sub)sequences.
  285.      The function returns SEQ1.
  286.      If SEQ1 and SEQ2 are `eq', then the replacement will work
  287.      correctly even if the regions indicated by the start and end
  288.      arguments overlap.  However, if SEQ1 and SEQ2 are lists which
  289.      share storage but are not `eq', and the start and end arguments
  290.      specify overlapping regions, the effect is undefined.
  291.  - Function: remove* ITEM SEQ &key :test :test-not :key :count :start
  292.           :end :from-end
  293.      This returns a copy of SEQ with all elements matching ITEM
  294.      removed.  The result may share storage with or be `eq' to SEQ in
  295.      some circumstances, but the original SEQ will not be modified.
  296.      The `:test', `:test-not', and `:key' arguments define the matching
  297.      test that is used; by default, elements `eql' to ITEM are removed.
  298.      The `:count' argument specifies the maximum number of matching
  299.      elements that can be removed (only the leftmost COUNT matches are
  300.      removed).  The `:start' and `:end' arguments specify a region in
  301.      SEQ in which elements will be removed; elements outside that
  302.      region are not matched or removed.  The `:from-end' argument, if
  303.      true, says that elements should be deleted from the end of the
  304.      sequence rather than the beginning (this matters only if COUNT was
  305.      also specified).
  306.  - Function: delete* ITEM SEQ &key :test :test-not :key :count :start
  307.           :end :from-end
  308.      This deletes all elements of SEQ which match ITEM.  It is a
  309.      destructive operation.  Since Emacs Lisp does not support
  310.      stretchable strings or vectors, this is the same as `remove*' for
  311.      those sequence types.  On lists, `remove*' will copy the list if
  312.      necessary to preserve the original list, whereas `delete*' will
  313.      splice out parts of the argument list.  Compare `append' and
  314.      `nconc', which are analogous non-destructive and destructive list
  315.      operations in Emacs Lisp.
  316.    The predicate-oriented functions `remove-if', `remove-if-not',
  317. `delete-if', and `delete-if-not' are defined similarly.
  318.  - Function: delete ITEM LIST
  319.      This MacLisp-compatible function deletes from LIST all elements
  320.      which are `equal' to ITEM.  The `delete' function is built-in to
  321.      Emacs 19; this package defines it equivalently in Emacs 18.
  322.  - Function: remove ITEM LIST
  323.      This function removes from LIST all elements which are `equal' to
  324.      ITEM.  This package defines it for symmetry with `delete', even
  325.      though `remove' is not built-in to Emacs 19.
  326.  - Function: remq ITEM LIST
  327.      This function removes from LIST all elements which are `eq' to
  328.      ITEM.  This package defines it for symmetry with `delq', even
  329.      though `remq' is not built-in to Emacs 19.
  330.  - Function: remove-duplicates SEQ &key :test :test-not :key :start
  331.           :end :from-end
  332.      This function returns a copy of SEQ with duplicate elements
  333.      removed.  Specifically, if two elements from the sequence match
  334.      according to the `:test', `:test-not', and `:key' arguments, only
  335.      the rightmost one is retained.  If `:from-end' is true, the
  336.      leftmost one is retained instead.  If `:start' or `:end' is
  337.      specified, only elements within that subsequence are examined or
  338.      removed.
  339.  - Function: delete-duplicates SEQ &key :test :test-not :key :start
  340.           :end :from-end
  341.      This function deletes duplicate elements from SEQ.  It is a
  342.      destructive version of `remove-duplicates'.
  343.  - Function: substitute NEW OLD SEQ &key :test :test-not :key :count
  344.           :start :end :from-end
  345.      This function returns a copy of SEQ, with all elements matching
  346.      OLD replaced with NEW.  The `:count', `:start', `:end', and
  347.      `:from-end' arguments may be used to limit the number of
  348.      substitutions made.
  349.  - Function: nsubstitute NEW OLD SEQ &key :test :test-not :key :count
  350.           :start :end :from-end
  351.      This is a destructive version of `substitute'; it performs the
  352.      substitution using `setcar' or `aset' rather than by returning a
  353.      changed copy of the sequence.
  354.    The `substitute-if', `substitute-if-not', `nsubstitute-if', and
  355. `nsubstitute-if-not' functions are defined similarly.  For these, a
  356. PREDICATE is given in place of the OLD argument.
  357. File: cl,  Node: Searching Sequences,  Next: Sorting Sequences,  Prev: Sequence Functions,  Up: Sequences
  358. Searching Sequences
  359. ===================
  360. These functions search for elements or subsequences in a sequence.
  361. (See also `member*' and `assoc*'; *note Lists::..)
  362.  - Function: find ITEM SEQ &key :test :test-not :key :start :end
  363.           :from-end
  364.      This function searches SEQ for an element matching ITEM.  If it
  365.      finds a match, it returns the matching element.  Otherwise, it
  366.      returns `nil'.  It returns the leftmost match, unless `:from-end'
  367.      is true, in which case it returns the rightmost match.  The
  368.      `:start' and `:end' arguments may be used to limit the range of
  369.      elements that are searched.
  370.  - Function: position ITEM SEQ &key :test :test-not :key :start :end
  371.           :from-end
  372.      This function is like `find', except that it returns the integer
  373.      position in the sequence of the matching item rather than the item
  374.      itself.  The position is relative to the start of the sequence as
  375.      a whole, even if `:start' is non-zero.  The function returns `nil'
  376.      if no matching element was found.
  377.  - Function: count ITEM SEQ &key :test :test-not :key :start :end
  378.      This function returns the number of elements of SEQ which match
  379.      ITEM.  The result is always a nonnegative integer.
  380.    The `find-if', `find-if-not', `position-if', `position-if-not',
  381. `count-if', and `count-if-not' functions are defined similarly.
  382.  - Function: mismatch SEQ1 SEQ2 &key :test :test-not :key :start1 :end1
  383.           :start2 :end2 :from-end
  384.      This function compares the specified parts of SEQ1 and SEQ2.  If
  385.      they are the same length and the corresponding elements match
  386.      (according to `:test', `:test-not', and `:key'), the function
  387.      returns `nil'.  If there is a mismatch, the function returns the
  388.      index (relative to SEQ1) of the first mismatching element.  This
  389.      will be the leftmost pair of elements which do not match, or the
  390.      position at which the shorter of the two otherwise-matching
  391.      sequences runs out.
  392.      If `:from-end' is true, then the elements are compared from right
  393.      to left starting at `(1- END1)' and `(1- END2)'.  If the sequences
  394.      differ, then one plus the index of the rightmost difference
  395.      (relative to SEQ1) is returned.
  396.      An interesting example is `(mismatch str1 str2 :key 'upcase)',
  397.      which compares two strings case-insensitively.
  398.  - Function: search SEQ1 SEQ2 &key :test :test-not :key :from-end
  399.           :start1 :end1 :start2 :end2
  400.      This function searches SEQ2 for a subsequence that matches SEQ1
  401.      (or part of it specified by `:start1' and `:end1'.)  Only matches
  402.      which fall entirely within the region defined by `:start2' and
  403.      `:end2' will be considered.  The return value is the index of the
  404.      leftmost element of the leftmost match, relative to the start of
  405.      SEQ2, or `nil' if no matches were found.  If `:from-end' is true,
  406.      the function finds the *rightmost* matching subsequence.
  407. File: cl,  Node: Sorting Sequences,  Prev: Searching Sequences,  Up: Sequences
  408. Sorting Sequences
  409. =================
  410.  - Function: sort* SEQ PREDICATE &key :key
  411.      This function sorts SEQ into increasing order as determined by
  412.      using PREDICATE to compare pairs of elements.  PREDICATE should
  413.      return true (non-`nil') if and only if its first argument is less
  414.      than (not equal to) its second argument.  For example, `<' and
  415.      `string-lessp' are suitable predicate functions for sorting
  416.      numbers and strings, respectively; `>' would sort numbers into
  417.      decreasing rather than increasing order.
  418.      This function differs from Emacs' built-in `sort' in that it can
  419.      operate on any type of sequence, not just lists.  Also, it accepts
  420.      a `:key' argument which is used to preprocess data fed to the
  421.      PREDICATE function.  For example,
  422.           (setq data (sort data 'string-lessp :key 'downcase))
  423.      sorts DATA, a sequence of strings, into increasing alphabetical
  424.      order without regard to case.  A `:key' function of `car' would be
  425.      useful for sorting association lists.
  426.      The `sort*' function is destructive; it sorts lists by actually
  427.      rearranging the `cdr' pointers in suitable fashion.
  428.  - Function: stable-sort SEQ PREDICATE &key :key
  429.      This function sorts SEQ "stably", meaning two elements which are
  430.      equal in terms of PREDICATE are guaranteed not to be rearranged
  431.      out of their original order by the sort.
  432.      In practice, `sort*' and `stable-sort' are equivalent in Emacs
  433.      Lisp because the underlying `sort' function is stable by default.
  434.      However, this package reserves the right to use non-stable methods
  435.      for `sort*' in the future.
  436.  - Function: merge TYPE SEQ1 SEQ2 PREDICATE &key :key
  437.      This function merges two sequences SEQ1 and SEQ2 by interleaving
  438.      their elements.  The result sequence, of type TYPE (in the sense
  439.      of `concatenate'), has length equal to the sum of the lengths of
  440.      the two input sequences.  The sequences may be modified
  441.      destructively.  Order of elements within SEQ1 and SEQ2 is
  442.      preserved in the interleaving; elements of the two sequences are
  443.      compared by PREDICATE (in the sense of `sort') and the lesser
  444.      element goes first in the result.  When elements are equal, those
  445.      from SEQ1 precede those from SEQ2 in the result.  Thus, if SEQ1
  446.      and SEQ2 are both sorted according to PREDICATE, then the result
  447.      will be a merged sequence which is (stably) sorted according to
  448.      PREDICATE.
  449. File: cl,  Node: Lists,  Next: Hash Tables,  Prev: Sequences,  Up: Top
  450. Lists
  451. *****
  452. The functions described here operate on lists.
  453. * Menu:
  454. * List Functions::                `caddr', `first', `last', `list*', etc.
  455. * Substitution of Expressions::   `subst', `sublis', etc.
  456. * Lists as Sets::                 `member*', `adjoin', `union', etc.
  457. * Association Lists::             `assoc*', `rassoc*', `acons', `pairlis'
  458. File: cl,  Node: List Functions,  Next: Substitution of Expressions,  Prev: Lists,  Up: Lists
  459. List Functions
  460. ==============
  461. This section describes a number of simple operations on lists, i.e.,
  462. chains of cons cells.
  463.  - Function: caddr X
  464.      This function is equivalent to `(car (cdr (cdr X)))'.  Likewise,
  465.      this package defines all 28 `cXXXr' functions where XXX is up to
  466.      four `a's and/or `d's.  All of these functions are `setf'-able,
  467.      and calls to them are expanded inline by the byte-compiler for
  468.      maximum efficiency.
  469.  - Function: first X
  470.      This function is a synonym for `(car X)'.  Likewise, the functions
  471.      `second', `third', ..., through `tenth' return the given element
  472.      of the list X.
  473.  - Function: rest X
  474.      This function is a synonym for `(cdr X)'.
  475.  - Function: endp X
  476.      Common Lisp defines this function to act like `null', but
  477.      signaling an error if `x' is neither a `nil' nor a cons cell.
  478.      This package simply defines `endp' as a synonym for `null'.
  479.  - Function: list-length X
  480.      This function returns the length of list X, exactly like `(length
  481.      X)', except that if X is a circular list (where the cdr-chain
  482.      forms a loop rather than terminating with `nil'), this function
  483.      returns `nil'.  (The regular `length' function would get stuck if
  484.      given a circular list.)
  485.  - Function: last X &optional N
  486.      This function returns the last cons, or the Nth-to-last cons, of
  487.      the list X.  If N is omitted it defaults to 1.  The "last cons"
  488.      means the first cons cell of the list whose `cdr' is not another
  489.      cons cell.  (For normal lists, the `cdr' of the last cons will be
  490.      `nil'.)  This function returns `nil' if X is `nil' or shorter than
  491.      N.  Note that the last *element* of the list is `(car (last X))'.
  492.  - Function: butlast X &optional N
  493.      This function returns the list X with the last element, or the
  494.      last N elements, removed.  If N is greater than zero it makes a
  495.      copy of the list so as not to damage the original list.  In
  496.      general, `(append (butlast X N) (last X N))' will return a list
  497.      equal to X.
  498.  - Function: nbutlast X &optional N
  499.      This is a version of `butlast' that works by destructively
  500.      modifying the `cdr' of the appropriate element, rather than making
  501.      a copy of the list.
  502.  - Function: list* ARG &rest OTHERS
  503.      This function constructs a list of its arguments.  The final
  504.      argument becomes the `cdr' of the last cell constructed.  Thus,
  505.      `(list* A B C)' is equivalent to `(cons A (cons B C))', and
  506.      `(list* A B nil)' is equivalent to `(list A B)'.
  507.      (Note that this function really is called `list*' in Common Lisp;
  508.      it is not a name invented for this package like `member*' or
  509.      `defun*'.)
  510.  - Function: ldiff LIST SUBLIST
  511.      If SUBLIST is a sublist of LIST, i.e., is `eq' to one of the cons
  512.      cells of LIST, then this function returns a copy of the part of
  513.      LIST up to but not including SUBLIST.  For example, `(ldiff x
  514.      (cddr x))' returns the first two elements of the list `x'.  The
  515.      result is a copy; the original LIST is not modified.  If SUBLIST
  516.      is not a sublist of LIST, a copy of the entire LIST is returned.
  517.  - Function: copy-list LIST
  518.      This function returns a copy of the list LIST.  It copies dotted
  519.      lists like `(1 2 . 3)' correctly.
  520.  - Function: copy-tree X &optional VECP
  521.      This function returns a copy of the tree of cons cells X.  Unlike
  522.      `copy-sequence' (and its alias `copy-list'), which copies only
  523.      along the `cdr' direction, this function copies (recursively)
  524.      along both the `car' and the `cdr' directions.  If X is not a cons
  525.      cell, the function simply returns X unchanged.  If the optional
  526.      VECP argument is true, this function copies vectors (recursively)
  527.      as well as cons cells.
  528.  - Function: tree-equal X Y &key :test :test-not :key
  529.      This function compares two trees of cons cells.  If X and Y are
  530.      both cons cells, their `car's and `cdr's are compared recursively.
  531.      If neither X nor Y is a cons cell, they are compared by `eql', or
  532.      according to the specified test.  The `:key' function, if
  533.      specified, is applied to the elements of both trees.  *Note
  534.      Sequences::.
  535. File: cl,  Node: Substitution of Expressions,  Next: Lists as Sets,  Prev: List Functions,  Up: Lists
  536. Substitution of Expressions
  537. ===========================
  538. These functions substitute elements throughout a tree of cons cells.
  539. (*Note Sequence Functions::, for the `substitute' function, which works
  540. on just the top-level elements of a list.)
  541.  - Function: subst NEW OLD TREE &key :test :test-not :key
  542.      This function substitutes occurrences of OLD with NEW in TREE, a
  543.      tree of cons cells.  It returns a substituted tree, which will be
  544.      a copy except that it may share storage with the argument TREE in
  545.      parts where no substitutions occurred.  The original TREE is not
  546.      modified.  This function recurses on, and compares against OLD,
  547.      both `car's and `cdr's of the component cons cells.  If OLD is
  548.      itself a cons cell, then matching cells in the tree are
  549.      substituted as usual without recursively substituting in that
  550.      cell.  Comparisons with OLD are done according to the specified
  551.      test (`eql' by default).  The `:key' function is applied to the
  552.      elements of the tree but not to OLD.
  553.  - Function: nsubst NEW OLD TREE &key :test :test-not :key
  554.      This function is like `subst', except that it works by destructive
  555.      modification (by `setcar' or `setcdr') rather than copying.
  556.    The `subst-if', `subst-if-not', `nsubst-if', and `nsubst-if-not'
  557. functions are defined similarly.
  558.  - Function: sublis ALIST TREE &key :test :test-not :key
  559.      This function is like `subst', except that it takes an association
  560.      list ALIST of OLD-NEW pairs.  Each element of the tree (after
  561.      applying the `:key' function, if any), is compared with the `car's
  562.      of ALIST; if it matches, it is replaced by the corresponding `cdr'.
  563.  - Function: nsublis ALIST TREE &key :test :test-not :key
  564.      This is a destructive version of `sublis'.
  565. File: cl,  Node: Lists as Sets,  Next: Association Lists,  Prev: Substitution of Expressions,  Up: Lists
  566. Lists as Sets
  567. =============
  568. These functions perform operations on lists which represent sets of
  569. elements.
  570.  - Function: member ITEM LIST
  571.      This MacLisp-compatible function searches LIST for an element
  572.      which is `equal' to ITEM.  The `member' function is built-in to
  573.      Emacs 19; this package defines it equivalently in Emacs 18.  See
  574.      the following function for a Common-Lisp compatible version.
  575.  - Function: member* ITEM LIST &key :test :test-not :key
  576.      This function searches LIST for an element matching ITEM.  If a
  577.      match is found, it returns the cons cell whose `car' was the
  578.      matching element.  Otherwise, it returns `nil'.  Elements are
  579.      compared by `eql' by default; you can use the `:test',
  580.      `:test-not', and `:key' arguments to modify this behavior.  *Note
  581.      Sequences::.
  582.      Note that this function's name is suffixed by `*' to avoid the
  583.      incompatible `member' function defined in Emacs 19.  (That
  584.      function uses `equal' for comparisons; it is equivalent to
  585.      `(member* ITEM LIST :test 'equal)'.)
  586.    The `member-if' and `member-if-not' functions analogously search for
  587. elements which satisfy a given predicate.
  588.  - Function: tailp SUBLIST LIST
  589.      This function returns `t' if SUBLIST is a sublist of LIST, i.e.,
  590.      if SUBLIST is `eql' to LIST or to any of its `cdr's.
  591.  - Function: adjoin ITEM LIST &key :test :test-not :key
  592.      This function conses ITEM onto the front of LIST, like `(cons ITEM
  593.      LIST)', but only if ITEM is not already present on the list (as
  594.      determined by `member*').  If a `:key' argument is specified, it
  595.      is applied to ITEM as well as to the elements of LIST during the
  596.      search, on the reasoning that ITEM is "about" to become part of
  597.      the list.
  598.  - Function: union LIST1 LIST2 &key :test :test-not :key
  599.      This function combines two lists which represent sets of items,
  600.      returning a list that represents the union of those two sets.  The
  601.      result list will contain all items which appear in LIST1 or LIST2,
  602.      and no others.  If an item appears in both LIST1 and LIST2 it will
  603.      be copied only once.  If an item is duplicated in LIST1 or LIST2,
  604.      it is undefined whether or not that duplication will survive in the
  605.      result list.  The order of elements in the result list is also
  606.      undefined.
  607.  - Function: nunion LIST1 LIST2 &key :test :test-not :key
  608.      This is a destructive version of `union'; rather than copying, it
  609.      tries to reuse the storage of the argument lists if possible.
  610.  - Function: intersection LIST1 LIST2 &key :test :test-not :key
  611.      This function computes the intersection of the sets represented by
  612.      LIST1 and LIST2.  It returns the list of items which appear in
  613.      both LIST1 and LIST2.
  614.  - Function: nintersection LIST1 LIST2 &key :test :test-not :key
  615.      This is a destructive version of `intersection'.  It tries to
  616.      reuse storage of LIST1 rather than copying.  It does *not* reuse
  617.      the storage of LIST2.
  618.  - Function: set-difference LIST1 LIST2 &key :test :test-not :key
  619.      This function computes the "set difference" of LIST1 and LIST2,
  620.      i.e., the set of elements that appear in LIST1 but *not* in LIST2.
  621.  - Function: nset-difference LIST1 LIST2 &key :test :test-not :key
  622.      This is a destructive `set-difference', which will try to reuse
  623.      LIST1 if possible.
  624.  - Function: set-exclusive-or LIST1 LIST2 &key :test :test-not :key
  625.      This function computes the "set exclusive or" of LIST1 and LIST2,
  626.      i.e., the set of elements that appear in exactly one of LIST1 and
  627.      LIST2.
  628.  - Function: nset-exclusive-or LIST1 LIST2 &key :test :test-not :key
  629.      This is a destructive `set-exclusive-or', which will try to reuse
  630.      LIST1 and LIST2 if possible.
  631.  - Function: subsetp LIST1 LIST2 &key :test :test-not :key
  632.      This function checks whether LIST1 represents a subset of LIST2,
  633.      i.e., whether every element of LIST1 also appears in LIST2.
  634. File: cl,  Node: Association Lists,  Prev: Lists as Sets,  Up: Lists
  635. Association Lists
  636. =================
  637. An "association list" is a list representing a mapping from one set of
  638. values to another; any list whose elements are cons cells is an
  639. association list.
  640.  - Function: assoc* ITEM A-LIST &key :test :test-not :key
  641.      This function searches the association list A-LIST for an element
  642.      whose `car' matches (in the sense of `:test', `:test-not', and
  643.      `:key', or by comparison with `eql') a given ITEM.  It returns the
  644.      matching element, if any, otherwise `nil'.  It ignores elements of
  645.      A-LIST which are not cons cells.  (This corresponds to the
  646.      behavior of `assq' and `assoc' in Emacs Lisp; Common Lisp's
  647.      `assoc' ignores `nil's but considers any other non-cons elements
  648.      of A-LIST to be an error.)
  649.  - Function: rassoc* ITEM A-LIST &key :test :test-not :key
  650.      This function searches for an element whose `cdr' matches ITEM.
  651.      If A-LIST represents a mapping, this applies the inverse of the
  652.      mapping to ITEM.
  653.  - Function: rassoc ITEM A-LIST
  654.      This function searches like `rassoc*' with a `:test' argument of
  655.      `equal'.  It is analogous to Emacs Lisp's standard `assoc'
  656.      function, which derives from the MacLisp rather than the Common
  657.      Lisp tradition.
  658.    The `assoc-if', `assoc-if-not', `rassoc-if', and `rassoc-if-not'
  659. functions are defined similarly.
  660.    Two simple functions for constructing association lists are:
  661.  - Function: acons KEY VALUE ALIST
  662.      This is equivalent to `(cons (cons KEY VALUE) ALIST)'.
  663.  - Function: pairlis KEYS VALUES &optional ALIST
  664.      This is equivalent to `(nconc (mapcar* 'cons KEYS VALUES) ALIST)'.
  665. File: cl,  Node: Hash Tables,  Next: Structures,  Prev: Lists,  Up: Top
  666. Hash Tables
  667. ***********
  668. A "hash table" is a data structure that maps "keys" onto "values."
  669. Keys and values can be arbitrary Lisp data objects.  Hash tables have
  670. the property that the time to search for a given key is roughly
  671. constant; simpler data structures like association lists take time
  672. proportional to the number of entries in the list.
  673.  - Function: make-hash-table &key :test :size
  674.      This function creates and returns a hash-table object whose
  675.      function for comparing elements is `:test' (`eql' by default), and
  676.      which is allocated to fit about `:size' elements.  The `:size'
  677.      argument is purely advisory; the table will stretch automatically
  678.      if you store more elements in it.  If `:size' is omitted, a
  679.      reasonable default is used.
  680.      Common Lisp allows only `eq', `eql', `equal', and `equalp' as
  681.      legal values for the `:test' argument.  In this package, any
  682.      reasonable predicate function will work, though if you use
  683.      something else you should check the details of the hashing
  684.      function described below to make sure it is suitable for your
  685.      predicate.
  686.      Some versions of Emacs (like Lucid Emacs 19) include a built-in
  687.      hash table type; in these versions, `make-hash-table' with a test
  688.      of `eq' will use these built-in hash tables.  In all other cases,
  689.      it will return a hash-table object which takes the form of a list
  690.      with an identifying "tag" symbol at the front.  All of the hash
  691.      table functions in this package can operate on both types of hash
  692.      table; normally you will never know which type is being used.
  693.      This function accepts the additional Common Lisp keywords
  694.      `:rehash-size' and `:rehash-threshold', but it ignores their
  695.      values.
  696.  - Function: gethash KEY TABLE &optional DEFAULT
  697.      This function looks up KEY in TABLE.  If KEY exists in the table,
  698.      in the sense that it matches any of the existing keys according to
  699.      the table's test function, then the associated value is returned.
  700.      Otherwise, DEFAULT (or `nil') is returned.
  701.      To store new data in the hash table, use `setf' on a call to
  702.      `gethash'.  If KEY already exists in the table, the corresponding
  703.      value is changed to the stored value.  If KEY does not already
  704.      exist, a new entry is added to the table and the table is
  705.      reallocated to a larger size if necessary.  The DEFAULT argument
  706.      is allowed but ignored in this case.  The situation is exactly
  707.      analogous to that of `get*'; *note Property Lists::..
  708.  - Function: remhash KEY TABLE
  709.      This function removes the entry for KEY from TABLE.  If an entry
  710.      was removed, it returns `t'.  If KEY does not appear in the table,
  711.      it does nothing and returns `nil'.
  712.  - Function: clrhash TABLE
  713.      This function removes all the entries from TABLE, leaving an empty
  714.      hash table.
  715.  - Function: maphash FUNCTION TABLE
  716.      This function calls FUNCTION for each entry in TABLE.  It passes
  717.      two arguments to FUNCTION, the key and the value of the given
  718.      entry.  The return value of FUNCTION is ignored; MAPHASH itself
  719.      returns `nil'.  *Note Loop Facility::, for an alternate way of
  720.      iterating over hash tables.
  721.  - Function: hash-table-count TABLE
  722.      This function returns the number of entries in TABLE.  *Warning:*
  723.      The current implementation of Lucid Emacs 19 hash-tables does not
  724.      decrement the stored `count' when `remhash' removes an entry.
  725.      Therefore, the return value of this function is not dependable if
  726.      you have used `remhash' on the table and the table's test is `eq'.
  727.      A slower, but reliable, way to count the entries is `(loop for x
  728.      being the hash-keys of TABLE count t)'.
  729.  - Function: hash-table-p OBJECT
  730.      This function returns `t' if OBJECT is a hash table, `nil'
  731.      otherwise.  It recognizes both types of hash tables (both Lucid
  732.      Emacs built-in tables and tables implemented with special lists.)
  733.    Sometimes when dealing with hash tables it is useful to know the
  734. exact "hash function" that is used.  This package implements hash
  735. tables using Emacs Lisp "obarrays," which are the same data structure
  736. that Emacs Lisp uses to keep track of symbols.  Each hash table
  737. includes an embedded obarray.  Key values given to `gethash' are
  738. converted by various means into strings, which are then looked up in
  739. the obarray using `intern' and `intern-soft'.  The symbol, or "bucket,"
  740. corresponding to a given key string includes as its `symbol-value' an
  741. association list of all key-value pairs which hash to that string.
  742. Depending on the test function, it is possible for many entries to hash
  743. to the same bucket.  For example, if the test is `eql', then the symbol
  744. `foo' and two separately built strings `"foo"' will create three
  745. entries in the same bucket.  Search time is linear within buckets, so
  746. hash tables will be most effective if you arrange not to store too many
  747. things that hash the same.
  748.    The following algorithm is used to convert Lisp objects to hash
  749. strings:
  750.    * Strings are used directly as hash strings.  (However, if the test
  751.      function is `equalp', strings are `downcase'd first.)
  752.    * Symbols are hashed according to their `symbol-name'.
  753.    * Integers are hashed into one of 16 buckets depending on their value
  754.      modulo 16.  Floating-point numbers are truncated to integers and
  755.      hashed modulo 16.
  756.    * Cons cells are hashed according to their `car's; nonempty vectors
  757.      are hashed according to their first element.
  758.    * All other types of objects hash into a single bucket named `"*"'.
  759. Thus, for example, searching among many buffer objects in a hash table
  760. will devolve to a (still fairly fast) linear-time search through a
  761. single bucket, whereas searching for different symbols will be very
  762. fast since each symbol will, in general, hash into its own bucket.
  763.    The size of the obarray in a hash table is automatically adjusted as
  764. the number of elements increases.
  765.    As a special case, `make-hash-table' with a `:size' argument of 0 or
  766. 1 will create a hash-table object that uses a single association list
  767. rather than an obarray of many lists.  For very small tables this
  768. structure will be more efficient since lookup does not require
  769. converting the key to a string or looking it up in an obarray.
  770. However, such tables are guaranteed to take time proportional to their
  771. size to do a search.
  772.